In this section, we will look at approaches towards solving the problem outlined
in Sec. \ref{sec:problem}: Modeling it as a linear-programming (LP) problem to
find an optimal solution, using a brute force local search and using various
local search algorithms to find good approximations of an optimal solution.

\input{3.1LP.tex} 

\subsection{Assignments} 

In order to be able to determine the quality of a current assignment, we 
need to design a data structure that represents an assignment. This data 
structure needs to be equipped with cost functions which return a 
discrete value determining the quality of the assignment. 

\subsubsection{Defining a State And Choosing a Data Structure} 
\label{subsubsec:datastruct} 

We use a data structure \textit{Schedule} for describing an assignment or
state. At initialization, the size of the schedule, i.e. number of departments,
types, days and slots per day, is given. The size of the array is the product of
all variables passed to \textit{Schedule} at initialization
time. \textit{Schedule} contains an array and accessor functions, which maps a
desired department, day, type and slot to an array index. Keeping all data in a
unified array is useful for quickly computing the cost of an assignment (see
Sec. \ref{subsubsec:cost}).

\textit{Schedule} is also used for representing the initial demand. 
Here, the schedule consists of only one department in which all shifts 
accumulate. 

\subsubsection{Evaluating State Cost}
\label{subsubsec:cost} 

\textit{Schedule} uses four functions to evaluate the cost of the 
assignment it represents. While one requires the cost of the given demand to
determine how well the given demand is met, two describe how equal shifts are
distributed amongst departments over a quarter and over each week. The last one
gives a penalty for exceeding a departments capability.

An option for weights is included, by adding a percentage multiplier 
index, detailed as a double array. Each value in the index corresponds to the 
specific departments ratio or $multiplier$. This multiplier index is modelled by 
the respective percentage of each value in a given weight index. 

\paragraph{Deviation Cost}
\label{par:deviation}

For computing how equal shifts are distributed, we compute the standard
deviation between departments for each type. This is done for the quarter by
accessing the part of the array that is valid for this department and type,
summing this part, utilizing the $multiplier$ and calculating the standard
deviation amongst these sums. The same premise is used for weekly deviation, by
also specifying the week when accessing part of the array.

The higher the standard deviation, the higher the cost of the assignment 
that is being evaluated. 

\paragraph{Demand Cost}
\label{par:demand}

In order to determine how well a demand is met, the function returns the
absolute difference between the number of demanded shifts and the number of
given shifts in the current assignment.

\paragraph{Capping Shifts}
\label{par:capping}

The cost function for capping, is implemented by adding a penalty for how much
the cap is exceeded. If weights are implemented, the $multiplier$ is utilized on
each shift.

\input{3.3brute-force.tex} 

\input{3.4localsearch.tex} 

